package leetcode.alg.demo;

/**
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 * 示例 1:
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 *
 * 示例 2:
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-product-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Maximum_product_subarray {
    public static void main(String[] args){
        int[] nums = {2,3,-2,4};
        System.out.println(maxProduct(nums));
    }

    /**
     * 动态规划，状态转移方程：
     *      dp_max[i] = Max{dp_max[i-1] * a(i), dp_min[i-1] * a(i), a(i)]}
     *      dp_min[i] = Min{dp_max[i-1] * a(i), dp_min[i-1] * a(i), a(i)]}
     *  动态规划需要考虑最小值，因为在转移过程中，过程中最大值乘负数变为最小值
     * @param nums
     * @return
     */
    private static int maxProduct(int[] nums){
        int max = Integer.MIN_VALUE;
        int max_tmp = 1;
        int min_tmp = 1;
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] < 0){
                int tmp = max_tmp;
                max_tmp = min_tmp;
                min_tmp = tmp;
            }
            max_tmp = Math.max(max_tmp * nums[i], nums[i]);
            min_tmp = Math.min(min_tmp * nums[i], nums[i]);
            max = Math.max(max, max_tmp);
        }
        return max;
    }
}
